#ifndef HYPERSPACE_H
#define HYPERSPACE_H

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <utility>
#include "hypercube.h"
#include "Clustering.h"
#include "DataImage.h"
using namespace std;

class HyperCube;

class HyperSpace {
    private:
        unsigned dimension;
        double sigma;
        double xi;
        unsigned int *upper_bounds;
        unsigned int *lower_bounds;
    public:
        typedef HyperCube space_hypercube;
        typedef map< string, space_hypercube> hypercube_container;
        typedef map< string, space_hypercube>::const_iterator hypercube_iterator;
    private:
        map< string, space_hypercube >   hypercubes;
        vector<string>   high_populated_keys;

        void createHyperCubes( const unsigned *num_partitions , const string&
                upp_bounds_str  , double edge_length){
            const string& curr_cube_key = upp_bounds_str;
            double *upp_bounds = HyperCube::getArrayFromKey( curr_cube_key , this->dimension);
            double low_bounds[this->dimension];
            for(unsigned i=0 ; i < this->dimension ; i++){
                low_bounds[i] = upp_bounds[i] - this->hypercubeEdgeLenght();
            }
            HyperCube* cube = new HyperCube( this->dimension, upp_bounds, this->hypercubeEdgeLenght() );
            HyperCube& curr_cube = *cube;
            vector<string> neighbors_keys;
            unsigned num_neighbors = (unsigned) pow(3*1.0 , this->dimension * 1.0);
            int neighbor[this->dimension];
            for(unsigned i=0 ; i < this->dimension; i++){
                neighbor[i] = -1;
            }
            for(unsigned i=0 ; i < num_neighbors; i++){
                bool outside_space = false;
                double next_upp_bounds[this->dimension];
                double next_low_bounds[this->dimension];
                for(unsigned dimension=0; dimension < this->dimension ; dimension++){
                    double increment = this->hypercubeEdgeLenght();
                    if( (upp_bounds[dimension] == this->upper_bounds[dimension]) && (neighbor[dimension] > 0) ){
                        outside_space = true;
                        break;
                    }
                    else if( (upp_bounds[dimension] == this->lower_bounds[dimension]) && (neighbor[dimension] < 0) ){
                        outside_space = true;
                        break;
                    }
                    next_upp_bounds[dimension] = upp_bounds[dimension] + ( neighbor[dimension] * increment );
                    if( (low_bounds[dimension] == this->lower_bounds[dimension]) && (neighbor[dimension] < 0) ){
                        outside_space = true;
                        break;
                    }
                    else if( (low_bounds[dimension] == this->upper_bounds[dimension]) && (neighbor[dimension] > 0) ){
                        outside_space = true;
                        break;
                    }
                    next_low_bounds[dimension] = low_bounds[dimension] + ( neighbor[dimension] * increment );
                }
                
                if( !outside_space ){
                    string neighbor_str_key = HyperCube::getKeyFromArray(
                            next_upp_bounds, this->dimension,
                            this->hypercubeEdgeLenght() );
                    if( neighbor_str_key != curr_cube_key ){  
                        
                        neighbors_keys.push_back(neighbor_str_key);
                    }
                }
                
                for( unsigned dimension = this->dimension ; dimension > 0 ; dimension--){
                    int index = dimension - 1;
                    if( neighbor[index] == -1 ){  neighbor[index] =  0;    break;  }
                    if( neighbor[index] ==  0 ){  neighbor[index] =  1;    break;  }
                    if( neighbor[index] ==  1 ){  neighbor[index] = -1;    }
                }
            }  

            
            curr_cube.setNeighbors( neighbors_keys );
            pair<string, HyperCube> *element = new pair<string,HyperCube>(curr_cube_key, curr_cube);
            this->hypercubes.insert( *element ); 
            delete cube;
            delete element;
            
            vector<string>::const_iterator it = neighbors_keys.begin();
            for( ; it != neighbors_keys.end() ; it++){
                
                if( this->hypercubes.count(*it) > 0 )  continue;
                else{
                    
                    HyperSpace::createHyperCubes( num_partitions , *it , this->hypercubeEdgeLenght() );
                }
            }
            delete[] upp_bounds;
        }

        double hypercubeEdgeLenght() const {  return (2 * this->sigma);  }

        double minimumObjectsInHypercubes() const {  return (this->xi / (2 *
                    this->dimension) );  }
    public:
        HyperSpace( const vector<unsigned int>& up_bound , const vector<unsigned int>& lw_bound, double sigma , double xi, const unsigned num_dimensions) {
            this->dimension = num_dimensions;
            this->sigma = sigma;
            this->xi = xi;
            
            this->lower_bounds = new unsigned int[num_dimensions];
            this->upper_bounds = new unsigned int[num_dimensions];
            double edge_length = this->hypercubeEdgeLenght();
            for(unsigned i=0 ; i < num_dimensions ; i++){
                this->lower_bounds[i] = lw_bound[i];
                this->upper_bounds[i] = edge_length * ceill(up_bound[i] / edge_length ); 
            }
        }

        HyperSpace( const HyperSpace& other ) {
            this->dimension = other.dimension;
            this->sigma = other.sigma;
            this->xi = other.xi;
            
            this->lower_bounds = new unsigned int[this->dimension];
            this->upper_bounds = new unsigned int[this->dimension];
            
            for(unsigned i=0 ; i < this->dimension ; i++){
                this->lower_bounds[i] = other.lower_bounds[i];
                this->upper_bounds[i] = other.upper_bounds[i];
            }
            
            this->hypercubes.clear();
            HyperSpace::hypercube_iterator it = other.hypercubes.begin();
            for( ; it != other.hypercubes.end() ; it++){
                this->hypercubes.insert(*it);
            }
        }

        ~HyperSpace(){
            
            delete[] this->upper_bounds;
            delete[] this->lower_bounds;
            this->hypercubes.clear();
        }

        const map< string, space_hypercube >* determineSpatialRegions(){
            unsigned num_partitions[this->dimension]; 
            unsigned long num_hypercubes = 1;   
            
            double edge_length = this->hypercubeEdgeLenght();
            
            for( unsigned i=0; i < this->dimension ; i++){
                num_partitions[i] = (unsigned) ceil((this->upper_bounds[i] -
                            this->lower_bounds[i]) / (edge_length));
                num_hypercubes = num_hypercubes * num_partitions[i];
            }
            
            double initial_upp_bounds[this->dimension];
            for(unsigned i=0 ; i < this->dimension ; i++){
                initial_upp_bounds[i] = this->lower_bounds[i] + this->hypercubeEdgeLenght();
            }
            
            string initial_upp_bounds_str = HyperCube::getKeyFromArray( initial_upp_bounds , this->dimension, this->hypercubeEdgeLenght() );
            
            this->createHyperCubes( num_partitions , initial_upp_bounds_str, this->hypercubeEdgeLenght() );
            
            return &(this->hypercubes);
        }

        void insertEntity( const DATA_ENTITY_CLASS_NAME& entity ){
            
            double attr_values[this->dimension];
            for(unsigned i=0 ; i < this->dimension ; i++){
                double sigma = this->hypercubeEdgeLenght();
                attr_values[i] = sigma * (floor( entity.getComponentValue(i) / sigma) + 1);
            }
            
            string key = HyperCube::getKeyFromArray( attr_values, this->dimension , this->hypercubeEdgeLenght());
            if( this->hypercubes.count(key) > 0 ){  
                this->hypercubes.find(key)->second.addObject(entity);
            }
            else {
                cerr << "[insertEntity] HyperCube for key (" << key << ") not found"<< endl;
            }
            return;
        }

        void removeLowPopulatedHypercubes(){
            
            vector<string> deleted_keys;
            this->high_populated_keys.clear();
            map< string, HyperCube>::iterator it = this->hypercubes.begin();
            while( it != this->hypercubes.end() ){
                
                if( it->second.numObjects() >= this->minimumObjectsInHypercubes() ){
                    this->high_populated_keys.push_back( it->first ); 
                }
                
                if( it->second.isEmpty() ){
                    deleted_keys.push_back(it->first); 
                    this->hypercubes.erase(it++);  
                }
                else ++it; 
            }
            
            it = this->hypercubes.begin();
            for( ; it != this->hypercubes.end() ; it++){

                it->second.removeEmptyNeighbors( deleted_keys );
            }
            
            it = this->hypercubes.begin();
            while( it != this->hypercubes.end() ){
                if( !(it->second.isNeighbor( high_populated_keys, this->hypercubes )) ){  
                    this->hypercubes.erase(it++);
                }
                else ++it;
            }
            return;
        }

        unsigned getNumEntities(void) const{
            unsigned num_entities = 0;
            
            hypercube_iterator iter = this->hypercubes.begin();
            while( iter != this->hypercubes.end() ){
                num_entities += iter->second.numObjects();
                iter++;
            }
            return num_entities;
        }

        class EntityIterator {
            private:
                HyperSpace* space;
                vector<string>::const_iterator cube_keys_iterator;
                vector<DATA_ENTITY_CLASS_NAME>::iterator entities_iterator;
            public:
                
                EntityIterator( HyperSpace& hs){
                    space = &hs;
                };
                
                ~EntityIterator(){};
                
                EntityIterator( const EntityIterator& other) {
                    space = other.space;
                    this->cube_keys_iterator = other.cube_keys_iterator;
                    this->entities_iterator = other.entities_iterator;
                }

                void begin(){
                    this->cube_keys_iterator = this->space->high_populated_keys.begin();
                    this->entities_iterator = this->space->hypercubes.find( *(this->cube_keys_iterator) )->second.retrieveObjects().begin();
                }

                void operator++(int){
                    
                    this->entities_iterator++;
                    if( this->entities_iterator == this->space->hypercubes.find( *(this->cube_keys_iterator) )->second.retrieveObjects().end() ){
                        
                        this->cube_keys_iterator++;
                        if( this->cube_keys_iterator != this->space->high_populated_keys.end() ){
                            this->entities_iterator = this->space->hypercubes.find( *(this->cube_keys_iterator) )->second.retrieveObjects().begin();
                        }
                    }
                }

                DATA_ENTITY_CLASS_NAME& operator*(){
                    return *entities_iterator;
                }

                DATA_ENTITY_CLASS_NAME* operator->(){
                    return &(*entities_iterator);
                }

                bool end(){
                    return (this->cube_keys_iterator == this->space->high_populated_keys.end());
                }

        };
        friend class EntityIterator;


};

#endif
